Shift 2D grid¶
Time: O(N); Space: O(1); easy
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation: * Element at grid[i][j] moves to grid[i][j + 1]. * Element at grid[i][n - 1] moves to grid[i + 1][0]. * Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:
Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Notes:
m == len(grid)
n == len(grid[i])
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
Hints:
Simulate step by step: move grid[i][j] to grid[i][j+1]. handle last column of the grid.
Put the matrix row by row to a vector. take k % len(vector) and move last k of the vector to the beginning. put the vector to the matrix back the same way.
[1]:
class Solution1(object):
def shiftGrid(self, grid, k):
"""
:type grid: List[List[int]]
:type k: int
:rtype: List[List[int]]
"""
def rotate(grids, k):
def reverse(grid, start, end):
while start < end:
start_r, start_c = divmod(start, len(grid[0]))
end_r, end_c = divmod(end-1, len(grid[0]))
grid[start_r][start_c], grid[end_r][end_c] = grid[end_r][end_c], grid[start_r][start_c]
start += 1
end -= 1
k %= len(grid)*len(grid[0])
reverse(grid, 0, len(grid)*len(grid[0]))
reverse(grid, 0, k)
reverse(grid, k, len(grid)*len(grid[0]))
rotate(grid, k)
return grid
[2]:
s = Solution1()
grid = [[1,2,3],[4,5,6],[7,8,9]]
k = 1
assert s.shiftGrid(grid, k) == [[9,1,2],[3,4,5],[6,7,8]]
grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]]
k = 4
assert s.shiftGrid(grid, k) == [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
grid = [[1,2,3],[4,5,6],[7,8,9]]
k = 9
assert s.shiftGrid(grid, k) == [[1,2,3],[4,5,6],[7,8,9]]